package com.tgy.algorithm.base._动态规划;

/**
 *
 * 给定一个数组，代表每个人喝完咖啡准备刷杯子的时间
 * 只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
 * 每个咖啡杯也可以自己挥发干净，时间耗费b，
 * 咖啡杯可以并行挥发
 * 返回让所有咖啡杯变干净的最早完成时间
 * 三个参数:int[l arr、int a、int bi
 */
public class _洗杯子 {


    //
    public static int clearCap(int[] arr, int clearTime,int volatilize) {


        return doClearCap(arr,clearTime,volatilize,0,0);
    }

    public static int doClearCap(int[] arr,int clearTime,int volatilize,int index,int canUseTime) {

        // 用咖啡机洗的洗完时间：Math.max(canUseTime,arr[index]) + clearTime
        // 挥发的时间 arr[index] + volatilize
        if (index == arr.length - 1) {
            // 最后一个的的时间，使用需要咖啡机洗和不需要咖啡机洗
            return Math.min(Math.max(canUseTime,arr[index])+clearTime,arr[index]+volatilize);
        }

        // 不需要咖啡机
       int value = Math.max(arr[index]+volatilize,doClearCap(arr,clearTime,volatilize,index+1,canUseTime));

        // 当前时间的咖啡机只能是喝完了咖啡的时间在咖啡机能使用之前
       int time = Math.max(canUseTime,arr[index]) + clearTime;
       time = Math.max(time,doClearCap(arr,clearTime,volatilize,index+1,time));

       return Math.min(value,time);
    }

    public static int clearCap01(int[] arr, int clearTime, int volatilize) {

        int len = arr.length;
        int canUseTime = 0;
        for (int i = 0; i < len; i++) {
            canUseTime = Math.max(canUseTime,arr[i]) + clearTime;
            System.out.println(canUseTime);
        }

//        System.out.println(canUseTime);
        int[][] dp = new int[len][canUseTime+1];

        for (int i = 0; i <= canUseTime; i++) {
            dp[len-1][i] = Math.min(Math.max(canUseTime,arr[len-1])+clearTime,arr[len-1]+volatilize);
        }

        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= canUseTime; j++) {
                // 不需要咖啡机
                int value = Math.max(arr[i]+volatilize,dp[i+1][j]);
                // 当前时间的咖啡机只能是喝完了咖啡的时间在咖啡机能使用之前
                int time = Math.max(canUseTime,arr[i]) + clearTime;
                if (time > clearTime) {
                    continue;
                }
                time = Math.max(time,dp[i+1][time]);
                dp[i][j] = Math.min(value,time);
            }
        }

        return dp[0][0];
    }

    public static void main(String[] args) {
        // 4 + 3 + 3 + 3 + 3 16
        int[] arr = {1,1,1,1,1,10};
//        clearCap01(arr,3,10);
        int min = clearCap(arr, 3, 10);
        System.out.println(min);
        int min01 = clearCap01(arr, 3, 10);
        System.out.println(min01);
    }
}
